package com.kevinkk.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
 * 叶子节点 是指没有子节点的节点。
 *
 * 递归遍历完所有的路径，然后检查有没有路径符合要求
 */

public class PathSum {
    class Solution {
        public boolean hasPathSum(TreeNode root, int targetSum) {
            if(root == null) return false;
            return traversal(root, targetSum, new ArrayList<Integer>());
        }

        private boolean traversal(TreeNode node, int targetSum, List<Integer> list){
            list.add(node.val);
            if(node.left == null && node.right == null){
                int sum = 0;
                for(int i : list) sum += i;
                return sum == targetSum;
            }
            boolean left = false, right = false;
            if(node.left != null){
                left = traversal(node.left, targetSum, list);
                list.remove(list.size()-1);
            }
            if(node.right != null){
                right = traversal(node.right, targetSum, list);
                list.remove(list.size()-1);
            }
            return left || right;
        }
    }
}
